package dp;

public class LC1132 {
    //一维数组
    public int minInsertions(String s) {
        int n=s.length();
        int[] dp=new int[n];
        for(int i=n-2;i>=0;i--){
            int pre=0;
            for(int j=i+1;j<n;j++){
                int temp=dp[j];
                if(s.charAt(i)==s.charAt(j)){
                    dp[j]=pre;
                }else{
                    dp[j]=Math.min(dp[j-1],dp[j])+1;
                }
                pre=temp;
            }
        }
        return dp[n-1];
    }
    //二维数组
//    public int minInsertions(String s) {
//        int n=s.length();
//        int[][] dp=new int[n][n];
//        for(int i=n-2;i>=0;i--){
//            for(int j=i+1;j<n;j++){
//                if(s.charAt(i)==s.charAt(j)){
//                    dp[i][j]=dp[i+1][j-1];
//                }else{
//                    dp[i][j]=Math.min(dp[i][j-1],dp[i+1][j])+1;
//                }
//            }
//        }
//        return dp[0][n-1];
//    }
}
